//! https://leetcode-cn.com/problems/remove-duplicate-letters/
//! 316. 去除重复字母
//! 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
//! 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
//! 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
pub struct Solution {}

#[allow(dead_code)]
impl Solution {
    pub fn remove_duplicate_letters(s: String) -> String {
        let mut res = Vec::new();
        let mut list = [false; 26];

        s.bytes().enumerate().for_each(|(i, c)| {
            if !list[c as usize - 97] {
                let t = s[i..].as_bytes();
                while !res.is_empty() && res[res.len() - 1] > c && t.contains(&res[res.len() - 1]) {
                    list[res.pop().unwrap() as usize - 97] = false;
                }
                res.push(c);
                list[c as usize - 97] = true
            }
        });

        String::from_utf8(res).unwrap()
    }
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(
            Solution::remove_duplicate_letters("bcabc".to_string()),
            "abc".to_string()
        );
    }
}
